export abstract class DerivationonSymbol {
    abstract get IsTerminal(): boolean;
    abstract get IsNonTerminal(): boolean;
    abstract get IsEpsilon(): boolean;
    private alias: string;

    get Alias(): string {
        return this.alias;
    }

    constructor(alias: string) {
        this.alias = alias;
    }

    toString(): string {
        return this.Alias
    }
}


/**
 * 非终结符
 */
export class TokenNonTerminator extends DerivationonSymbol {
    get IsNonTerminal(): boolean {
        return true;
    }
    get IsTerminal() {
        return false;
    }
    get IsEpsilon() {
        return false;
    }
}


/**
 * 终结符
 */
export class TokenTerminator extends DerivationonSymbol {
    get IsNonTerminal(): boolean {
        return false;
    }
    get IsTerminal() {
        return true;
    }
    get IsEpsilon() {
        return false;
    }
}

/**
 * 空串
 */
export class TokenEpsilon extends DerivationonSymbol {
    get IsNonTerminal(): boolean {
        return false;
    }
    get IsTerminal() {
        return false;
    }
    get IsEpsilon() {
        return true;
    }
}


/**
 * Epsilon 
 * ε 代表空串
 */
export const DerivationonSymbolEpsilon: TokenTerminator = new TokenEpsilon("ε");


/**
 * 代表 EOF
 */
export const DerivationonTokenEOF: TokenTerminator = new TokenEpsilon("#");

export type GrammarToken = TokenTerminator | TokenNonTerminator | TokenEpsilon

export interface AbEqualToOther {
    equalToOther(other: AbEqualToOther): boolean;
}

export function EqualToEqualToOther(a: AbEqualToOther, b: AbEqualToOther) {
    if (a === b) {
        return true;
    }
    if (a === null || b === null) {
        return false;
    }

    return a.equalToOther(b);
}

/**
 * 推导式  A -> ( A )
 */
export class Derivation {
    left: TokenNonTerminator
    right: GrammarToken[]
    constructor(left: TokenNonTerminator, right: GrammarToken[]) {
        this.left = left;
        this.right = right;
    }

    toString(): string {
        return `${this.left} → ${this.right.join(" ")}`
    }
}



/**
 * 是否所有都满足。 当长度为0时，返回true
 */
function isAll<T>(iterable: T[], judge: (item: T) => boolean): boolean {
    for (let item of iterable) {
        if (!judge(item)) {
            return false;;
        }
    }
    return true;
}

/**
 * 是否任意一个满足。 当长度为0时，返回 false
 */
function isAny<T>(iterable: T[], judge: (item: T) => boolean): boolean {
    for (let item of iterable) {
        if (judge(item)) {
            return true;;
        }
    }
    return false;
}


/**
 * 语法： 终结符号, 非终结符号, 推导式, 开始符号
 */
export class Grammar {
    /**
     * 非终结符号
     */
    vn: GrammarToken[]

    /**
     * 终结符号
     */
    vt: GrammarToken[]

    /**
     * 推导式
     */
    pList: Derivation[]

    /**
     * 开始符号
     */
    s: GrammarToken


    constructor(vn: GrammarToken[], vt: GrammarToken[], pList: Derivation[], s: GrammarToken) {
        this.vt = vt;
        this.vn = vn;
        this.pList = pList;
        this.s = s;
        this.Vaildate();
    }


    /**
     * 从推导式列表创建语法
     * @TODO 校验语法是否合法？ 
     */
    static NewFromDerivationList(pList: Derivation[], s: GrammarToken): Grammar {
        const tokens = new Set<GrammarToken>();
        for (let d of pList) {
            tokens.add(d.left);
            for (let t of d.right) {
                tokens.add(t)
            }
        }

        const vlist = [...tokens];
        const vt = vlist.filter(item => item.IsTerminal);
        const vn = vlist.filter(item => item.IsNonTerminal);
        return new Grammar(vn, vt, pList, s);
    }

    /**
     * 校验语法是否合法？ 
     */
    Vaildate() {
        // 左侧符号不为空，右边的每个符号也不为空
        // 右边至少长度为 1

        // 1. 左边的都是非终结符，存在终结符则报错
        // 2. 非终结符都在左侧出现过
        // 3. 开始符号在之中、开始符号为非终结符

        // 4. 除开自己可以引用自己，如果没有其他额外的推导式，那么报错
        //     比如：  B -> a B c
        //            但是没有  B ->  E 

        // 5. 所有非终结符必须可推导


    }

    /**
     * 验证语法的可推导性
     */
    VaildateCanProduceAtLastOne(): {
        success: boolean,
        errorMessage?: string,
        errorDervationList?: Derivation[],
    } {
        const derivationMap = this.BuildDerivationMap();
        const canPud = new Set<Derivation>();

        /**
         * @param d 已在推导队列中的
         */
        function recsu(cur: Derivation, alreadySet: Set<Derivation>): boolean {
            if (canPud.has(cur)) {
                return true;
            }


            // 是否右边都能推出来
            for (let token of cur.right) {
                if (token.IsTerminal || token.IsEpsilon) { // 可被推导
                    continue;
                }

                const isAnyOk = isAny([...(derivationMap.get(token) ?? new Set())], (item) => {
                    if (alreadySet.has(item)) {
                        return false;
                    }
                    alreadySet.add(item);
                    const trres = recsu(item, alreadySet);
                    alreadySet.delete(item);
                    return trres;
                });

                // 任意可推导？
                if (!isAnyOk) {
                    return false;
                }
            }

            return true;
        }


        const errorDervationList: Derivation[] = [];
        for (let d of this.pList) {
            const isOk = recsu(d, new Set([d]));
            if (!isOk) {
                errorDervationList.push(d);
            } else {
                canPud.add(d);
            }
        }

        if (errorDervationList.length > 0) {
            return {
                success: false,
                errorMessage: "无法推导推导式",
                errorDervationList,
            };
        }

        return {
            success: true,
        };
    }

    toString(): string {
        return this.pList.join("\n")
    }

    /**
     * 
     * 构建 key 为非终结符， value 为 这个非终结符相关 推导式的 set 的 map
     */
    BuildDerivationMap(): Map<GrammarToken, Set<Derivation>> {
        let theMap = new Map<GrammarToken, Set<Derivation>>();

        for (const d of this.pList) {
            const set = theMap.get(d.left) ?? new Set<Derivation>();
            set.add(d);
            theMap.set(d.left, set);
        }
        return theMap;
    }

    /**
     * 计算非终结符的 Follow 集
     */
    CalcuateNonTerminatorFollowSet(): Map<GrammarToken, Set<GrammarToken>> {
        const firstF = this.CalcuateNonTerminatorFirstFunc();

        const followSetMap = new Map<GrammarToken, Set<GrammarToken>>();
        const follow = (token: GrammarToken, queryedPath: Set<GrammarToken>): Set<GrammarToken> => {
            const alreadySet = followSetMap.get(token);
            if (alreadySet) {
                return alreadySet;
            }

            // // 查看是否在内 ？
            // if (queryedPath.has(token)) {
            //     return new Set();
            // }

            const theSet = new Set<GrammarToken>();
            // 1. 若A是开始符号，则 EOF 就在 Follow(A)中。
            if (token === this.s) {
                theSet.add(DerivationonTokenEOF);
            }

            // 2. 若存在产生式B → αAγ，则 First(γ) - {ε} 在 Follow(A) 中。
            for (let d of this.pList) {
                const theD_Left = d.left;
                const theD_Right = d.right;
                for (let i = 0; i < theD_Right.length; i++) {
                    const t = theD_Right[i];
                    if (t === token) { // ...
                        const grAry = theD_Right.slice(i + 1, theD_Right.length);
                        const retSet = firstF(grAry);

                        // 3. 若存在产生式B→αAγ，且在 First(γ)中存在ε,(也可称为γ能推导出ε)，则 Follow(A) 包括 Follow(B) 。
                        if (retSet.has(DerivationonSymbolEpsilon)) {
                            retSet.delete(DerivationonSymbolEpsilon);

                            if (!queryedPath.has(theD_Left)) {
                                queryedPath.add(theD_Left);
                                const theLeftCdSet = follow(theD_Left, queryedPath);
                                if (!followSetMap.has(theD_Left)) { // Cache it
                                    followSetMap.set(theD_Left, theLeftCdSet);
                                }
                                theLeftCdSet.forEach(item => theSet.add(item));
                                queryedPath.delete(theD_Left);
                            }
                        }
                        retSet.forEach(item => theSet.add(item));
                    }
                }
            }

            return theSet;
        }

        for (let tn of this.vn) {
            followSetMap.set(tn, follow(tn, new Set([tn])));
        }

        return followSetMap;
    }

    /**
     * 计算非终结符的 First 集
     */
    CalcuateNonTerminatorFirstSet(): Map<GrammarToken, Set<GrammarToken>> {
        const derivationMap = this.BuildDerivationMap();
        const canProduceEpsilonSet = this.CalculateVtThatCanProduceEpsilon();
        canProduceEpsilonSet.add(DerivationonSymbolEpsilon);

        // 定义：令X为一个文法符号（一个终结符或非终结符）或 ，则集合First (X) 由终结符组成，此外可能还有 ε，它的定义如下：
        // 1. 若X是终结符或 ，则First (X) = {X}
        // 2. 若X是非终结符，则对于每个产生式 X→X1 X2 . . . Xn ，First(X)都包含了 First(X1) - {ε}。
        //    若对于某个i < n，所有的集合First (X1 ), . . . , First (Xi) 都包括了 ε
        //    ，则First (X) 也包括了First (Xi + 1) - { ε }。
        //    若所有集合First (X1 ), . . . , First (Xn) 包括了 ，则First (X)也包括 。

        const firstSetMap = new Map<GrammarToken, Set<GrammarToken>>();
        function first(queryPath: GrammarToken[]): Set<GrammarToken> {
            const t = queryPath[queryPath.length - 1];

            // 是否是终结符或者 ε
            if (t === DerivationonSymbolEpsilon || t.IsTerminal) {
                const s = new Set<GrammarToken>();
                s.add(t);
                return s;
            }

            // 是否已经求过？
            let theSet = firstSetMap.get(t);
            if (theSet) {
                return theSet;
            }

            // 判断表达式
            const derivationList = derivationMap.get(t);
            if (!derivationList) {
                throw new Error("无法推导的语法！");
            }

            let tokenBox = new Set<GrammarToken>();
            let needContainsEpsilon = false;

            // 对每个推导式来说
            for (let d of derivationList) {

                // 寻找第一个不能推出 ε 的非终结符的位置
                for (let idx = 0; idx < d.right.length; idx++) {
                    const s = d.right[idx];

                    // 遇到已经在求值的跳过
                    if (queryPath.includes(s)) {
                        continue;
                    }

                    // 进行 First 求值
                    queryPath.push(s);
                    const retSet = first(queryPath);
                    // cache赋予？
                    if (s.IsNonTerminal && !firstSetMap.has(s)) {
                        firstSetMap.set(s, new Set(retSet));
                    }
                    queryPath.pop();

                    // 是否不能能推导出 ε ?
                    if (!canProduceEpsilonSet.has(s)) {
                        retSet.forEach(item => tokenBox.add(item));
                        break;
                    }

                    // 能推出 ε ，继续找
                    retSet.delete(DerivationonSymbolEpsilon);
                    retSet.forEach(item => tokenBox.add(item));

                    // 是否是最后一个了？
                    if (idx + 1 == d.right.length) {
                        needContainsEpsilon = true;
                    }
                }
            }

            if (needContainsEpsilon) {
                tokenBox.add(DerivationonSymbolEpsilon); // 包含 ε
            }

            return tokenBox;
        }


        for (let s of this.vn) {
            firstSetMap.set(s, first([s]));
        }


        return firstSetMap;
    }

    CalcuateNonTerminatorFirstFunc(): (tokenList: GrammarToken[]) => Set<GrammarToken> {
        const firstSetMap = this.CalcuateNonTerminatorFirstSet();
        // 输入
        function finalFunc(tokenList: GrammarToken[]): Set<GrammarToken> {
            // 空串则返回空串
            if (tokenList.length == 0) {
                return new Set([DerivationonSymbolEpsilon]);
            }

            const theSet = new Set<GrammarToken>();
            // 寻找第一个不能推出 ε 的非终结符的位置
            for (let idx = 0; idx < tokenList.length; idx++) {
                const token = tokenList[idx];

                // 是否是空串
                if (token.IsEpsilon) {
                    theSet.add(DerivationonSymbolEpsilon);
                    break;
                }

                // 是否是终结符
                if (token.IsTerminal) {
                    theSet.add(token);
                    break;
                }

                // 此时为非终结符
                const srcSet = firstSetMap.get(token) ?? new Set();
                srcSet.forEach(item => theSet.add(item));

                // Fisrt(A) 不能推出 ε
                if (!srcSet.has(DerivationonSymbolEpsilon)) {
                    break;
                }

                // 表达式能推出 ε， 那么查看是否是最后一个
                if (idx + 1 == tokenList.length) {
                    theSet.add(DerivationonSymbolEpsilon);
                }
            }
            return theSet;
        }

        return finalFunc;
    }

    /**
     * 计算能推导出 ε 的非终结符集合
     * @returns 返回可推出 ε
     * @TODO 可优化?
     */
    CalculateVtThatCanProduceEpsilon(): Set<GrammarToken> {
        const canProduceEpsilonSet = new Set<GrammarToken>();
        const cannotProduceEpsilonSet = new Set<GrammarToken>();
        let unknowMap = this.BuildDerivationMap();


        while (unknowMap.size > 0) {
            let anyChange = false;
            for (let nts of [...unknowMap.entries()]) {
                // 非终结符 nts
                const theLeft = nts[0];
                const theDerivationSet = nts[1];

                for (let d of [...theDerivationSet]) {
                    const theRight = d.right;
                    const theRightWithoutSelf = theRight.filter(item => item != theLeft);

                    //  是否能推导出非空
                    const isAnyTerminal = isAny(theRightWithoutSelf, item => item.IsTerminal || cannotProduceEpsilonSet.has(item));
                    if (isAnyTerminal) {
                        anyChange = true;
                        // 移除自己这一项
                        theDerivationSet.delete(d);

                        // 表示此表达式 能推导出非空 。
                        // 如果是推导式的最后一项则表示左边的非终结符不可以推出空串
                        if (theDerivationSet.size == 0) {
                            cannotProduceEpsilonSet.add(theLeft);
                            unknowMap.delete(theLeft);
                            break;
                        }
                        continue;
                    }

                    // 是否能推导出空
                    const allIsEmtpy = isAll(theRightWithoutSelf, item => item === DerivationonSymbolEpsilon || (item.IsNonTerminal && canProduceEpsilonSet.has(item)));
                    if (allIsEmtpy) {
                        anyChange = true;
                        canProduceEpsilonSet.add(theLeft);
                        unknowMap.delete(theLeft);
                        break;
                    }
                }
            }

            if (!anyChange) {
                throw new Error("无法处理的语法推导式");
            }
        }

        return canProduceEpsilonSet;
    }


}




